class Solution {
public:
    bool vis[300][300];
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    int m, n,ret;
    typedef struct tmp{
        int x;
        int y; 
    }tmp;
    void bfs(vector<vector<char>>& grid,queue<tmp>& q){
        while(!q.empty()){
            tmp temp=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int nx=temp.x+dx[i],ny=temp.y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&!vis[nx][ny]&&grid[nx][ny]=='1'){
                    vis[nx][ny]=1;
                    q.push({nx,ny});
                }
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        queue<tmp> q;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'&&!vis[i][j]){
                    ret++;
                    vis[i][j]=1;
                    q.push({i,j});
                    bfs(grid,q); //Ⱦɫ
                }
            }
        }
        return ret;
    }
};
